package bintree.my_bin_tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author yuisama
 * @version 1.0.0
 * @Description BST与链表插入与查询的性能测试
 * @createTime 2023年04月04日 15:03:00
 */
public class PerformanceTest {
    static ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void main(String[] args) {
        int n = 10_0000;
        int[] arr1 = generateSortedArray(n,50);
        int[] arr2 = arrCopy(arr1);
        LinkedList<Integer> linkedList = new LinkedList<>();
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        // 测试插入效率
        long start = System.nanoTime();
        for (int i : arr1) {
            linkedList.add(i);
        }
        long end = System.nanoTime();
        System.out.println("链表插入" + n + "个数字共耗时:" + (end - start) / 1000000.0 + "ms");
        start = System.nanoTime();
        for (int i : arr2) {
            bst.add(i);
        }
        end = System.nanoTime();
        System.out.println("BST插入" + n + "个数字共耗时:" + (end - start) / 1000000.0 + "ms");
        // 测试查询效率
        start = System.nanoTime();
        System.out.println(linkedList.contains(789651));
        end = System.nanoTime();
        System.out.println("链表查询某个数字共耗时:" + (end - start) / 1000000.0 + "ms");
        start = System.nanoTime();
        System.out.println(bst.contains(789651));
        end = System.nanoTime();
        System.out.println("BST查询某个数字共耗时:" + (end - start) / 1000000.0 + "ms");
    }


    /**
     * 生成一个大小为n的近乎有序的数组
     * @param n
     * @param swapTimes
     * @return
     */
    public static int[] generateSortedArray(int n,int swapTimes) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        for (int i = 0; i < swapTimes; i++) {
            int x = random.nextInt(0,n);
            int y = random.nextInt(0,n);
            swap(arr,x,y);
        }
        return arr;
    }

    private static void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * 生成一个大小为n，在范围[l..r)上的随机数组
     * @param n
     * @return
     */
    public static int[] generateRandomArray(int n,int l,int r) {
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = random.nextInt(l,r);
        }
        return result;
    }

    public static int[] arrCopy(int[] arr) {
        return Arrays.copyOf(arr,arr.length);
    }
}
